This invention relates generally to expert systems, and more particularly to an expert system for processing knowledge concerning a large-scale artificial system.
Various systems have been proposed for expert systems that store knowledge of human experts in a knowledge base and make judgments similar to those of the human experts. Currently, the most popular inference method is a so-called production system. Other methods use frames to represent knowledge.
In some of these production systems, the method used is to perform forward reasoning, while in other production systems, the method used is to perform backward reasoning. The production system for performing forward reasoning is a system in which the cycle of recognition and action of a human is modeled. Namely, this kind of production system recognizes the current status and then determines the content of the next action.
FIG. 2 of the accompanying drawings shows the general structure of this production system. As shown in FIG. 2, the production system generally comprises a knowledge base 201 and an inference engine 202. Inside the knowledge base 201 there are included a plurality of rules 203, a plurality of knowledge representations, e.g. a plurality of frames 204, and a work area 205.
The rules 203 include a condition section, which contains condition instructions for recognizing the status stored in the frames 204 or the work area 205, and an instruction section in which the action to be executed is described. Using these rules, the inference engine 202 repeats three steps to execute an inference, i.e. matching process 206, conflict resolution 207 and action 208.
The matching process 206 in the inference engine 202 is the step of retrieving the rules that have condition instructions which match the current status stored in the work area 203 or the frames 205 and then integrating a set of both the matching rules and the status values as a conflict set 209. The conflict resolution 207 is the step of selecting one rule to be executed from the obtained conflict set 209. The action 208 is the step of executing, such as the updating of the content of the work area or the frames, according to the description in the instruction section of the selected rule.
The frames representing knowledge are frames for systematically and hierarchically representing information concerning a knowledge processing object. FIG. 3 shows an example in which knowledge concerning components of an electric circuit is hierarchically represented by frames.
In FIG. 3, a frame 301 of the uppermost class defines an attribute of class as electrical components. In the illustrated example, the frame of electrical components, which define the class of electrical components, has two slots, i.e., name of manufacturing company 302 and date of production 303. Lower frames 304, 305, 306 preceding frame 301 define classes of more specific types of entries, such as resistor 304, coil 305 and condenser 306.
The frame of resistor 304, which defines the class of resistor, has the type of resistor 307 as a slot for storing the type of resistor and has the resistance 308 as a slot for storing the resistance of the resistor.
Thus frames 309, 310 represent knowledge about individual components as follows:
Component R1 of the frame 309 has resistor as class, and hence has type of resistor and resistance, which are slots defined in class of resistor.
The class of resistor 304 of component R1 in the frame 309 is a lower class subordinate to the electrical component 301, and hence succeeds also to the attribute of the electrical component 301, having two slots, i.e. manufacturing company 302 and date of production 303, which are defined in the class of electrical components. Then the actual name of a company and other information are stored in the respective slots to express information about an individual electrical component. The frames are stored in a data base systematically storing data as described above and are capable of storing a process specific to the frames.
FIG. 4 shows an example in which a process specific to the frame is stored by a function called demon and a function called method. In FIG. 4, in the frame fr1, slots S11 and S12 are defined and have stored in them the values 10 and 5, respectively.
In the slot S11, the procedure func1 having a character `when-changed` is defined as a demon, while in the slot S12, the procedure func2 having a character `when-asked` is also defined as a demon.
The character `when-asked` executes when the slot value stored in the slot is referred to externally, while the character `when-changed` executes when the slot value is updated. Therefore, when the value of the slot S11 is updated, the procedure func1 is executed with the value of the slot S11 as an argument. Also in FIG. 4, func3 is a procedure called method which is a procedure effective only in the frame fr1.
The method func3 is executed by giving the name of method `func3` as a message passed to the frame fr1 from an external source. After executing the defined processes, the method func3 returns the value of the executed result back as a reply to the frame or rule that sent the message.
As discussed above, a production system is a simple but very general technique. Since frames can systematically represent knowledge, they are widely used in expert systems. However, assuming that the conventional production system and frames are applied to an actual large-scale plant or an artificial large-scale system, such as power, communications or transportation networks, a practical inference speed cannot be achieved.
These problems will now be described item by item in greater detail.
(1) Increase of Time Needed for Condition Judgment called matching process
An inference cycle of the production system is simple and can serve a general purpose. Assuming that this inference cycle is realized progressively on a computer, the amount of computation for condition judgment will increase exponentially as the number of frames is increased.
Accordingly algorithms have hitherto been proposed for increasing the rate of condition judgment of the production system. A typical algorithm is the RETE algorithm. Recently, for example, the TREAT algorithm which is an improvement of the RETE algorithm has been announced. The RETE algorithm is discussed in Forgy, C. L.: RETE, A Fast Algorithm for the Many Pattern/Many Object Pattern Matching Problem, Artificial Knowledge, Vol. 19, pp 17-37. TREAT algorithm is discussed in Miranker, D. P.: The TREAT, A Better Match Algorithm for AI Production Systems, AAAI-87, pp 42-47. Furthermore, these algorithms are explained in an article in the Journal of the Inference Processing Society of Japan, Vol. 29, No. 5, page 467.
In short, one feature of condition judgment algorithms, including the RETE algorithms, is that the number of condition judgments is reduced by previously analyzing rules to provide a combination of rules having a common condition clause, constituting a data flow graph called `RETE network` or "rule network` and commonly using the flow graph for computation of the individual condition clause. Another feature of such condition judgment algorithms is that the interim result of conditional judgment is computed by recomputing only the portion influenced by the previous execution step and combining that portion with an interim result unchanged from the previous execution, reserving the interim result of the preceding inference cycle.
The movement of this RETE algorithm will now be described in connection with a simple rule shown in FIG. 5. In FIG. 5, a term with question mark (?) affixed at its head represents a variable, and a term with an at sign (@) affixed at its head represents a value of a designated slot. An arrow (.fwdarw.) indicates the value to be substituted. ?FR1 and ?FR2 in the condition section of the rules are variables representing the names of frames, and ?v is a variable to be substituted by the value of slot `value`. Therefore, Rule 1 represents the rule: execute the instruction section if there is a frame ?FR1 in which the class is c1, the value of slot `limit` (slot kind identification No.) is 10 and if there is a frame ?FR2 in which the class is c2, the value of slot `limit` is 20, and the value of slot `value` is larger than ?v (i.e., larger than @ value of ?FR1).
Rule 2 represents the rule: execute the instruction section if there is a frame ?FR1 in which the class is c1, the value of slot `limit` (slot kind identification No.) is 10 and if there is a frame ?FR2 in which the class is c2, the value of slot `limit` is 20, and the value of slot `value` is smaller than ?v (i.e., larger than @ value of ?FR1 ). And, there exist frames {f11, f12, f13, f14, f21, f22, f23, f24}. As shown in FIG. 5, {f11, f12, f13, f14} belongs to the class c1, and {f21, f22, f23, f24}belongs to the class c2. FIG. 6 shows the condition section of the rule of FIG. 5 as a rule network.
The RETE algorithm will now be described in connection with FIG. 6. In the rule network, the portion in which the individual condition clause is to be judged is represented by a node.
In FIG. 6, 601 designates a route node serving as an inlet from which a frame, which is to be judged, flows into the rule network; 602, a node at which the judgment is to be made as to whether the class of frame is c1 or not; and 603, a node at which the judgment is to be made as to whether the class of frame is c2 or not. 604 designates a node at which the judgment is to be made as to whether the value of slot `limit` is 10 or not; and 605, a node at which the judgment is to be made as to whether the value of slot `limit` is 20 or not. 606 designates a node at which the judgment is to be made as to whether the value of slot `value` of ?FR1 is smaller than the value of slot `value` of ?FR2; and 607, a node at which the judgment is to be made as to whether the value of slot `value` of ?FR1 is larger than or equal to the value of slot `value` of ?FR2. The nodes 602 through 605 are called "intranodes", while the nodes 606 and 607 are called "internodes".
A set of frames {f11, f12, f13, f14, f21, f22, f23, f24} to be judged is let to flow from the route node 601 to the rule network; the frame matched with the condition judgment at each node is stored in that node and is transmitted to the next node via a branch. 608 designates a set of frames matched with the condition judgment of the node 602; 609, a set of frames matched with the condition judgment of the node 603; 610, a set of frames matched with the condition judgment of the node 604; and 611, a set of frames matched with the condition judgment of the node 605.
The internode 606 combines the frames passed from the condition judgment of the intranodes 604 and 605 to judge a set of frames matched with the condition of Rule 1. The arithmetic operation at the node 606 is to obtain a combination of two sets of frames by a JOIN operation, the result of the operation being designated by 612. The first set of frames {f11, f21} 612 shows that f11 match with the frame names ?FR1 of the first condition clause of Rule 1 and f21 match with the frame names ?FR2 of the 2nd condition clause of Rule 1, and that the condition section of Rule 1 is satisfied by the combination of them.
Of a set of frames stored at each node, the frames stored in the intranode are called ".alpha. memory", and the frames stored in the internode are called ".beta. memory". Now assume that the slot values of frames f12, 123, 124 are varied as shown in FIG. 7 by adoption of a rule. In this case, in the RETE algorithm, the updated frames are canceled from both .alpha. memory and .beta. memory of the rule network, whereupon the further updated frames are let to flow from the route node to the rule network, to be recomputed and to reconstitute the interim memory (.alpha. memory and .beta. memory).
FIG. 8 shows the varied interim memory of each node after performing this reconstitution work. Since the amount of computation required for reconstitution of this interim memory is increased in an applied field such that the interim result of the previous cycle is changed markedly by the rule execution, the RETE algorithm cannot adequately be effective in applied fields to increase the rate of condition judgments.
To cancel the updated frames from both .alpha. memory and .beta. memory, it must be determined which node the frame is stored in. This can be realized usually by letting the frame, while keeping its previous value, flow in the rule network and by canceling data about the frame from the memory of the reached node. Then the updated value of the frame is allowed to flow through into the network.
In reconstituting the interim memory, as the number of frames that are updated increases, the computation increases. Partly since a practical large-scale plant or an artificial large-scale system, such as electrical power, communications or transportation network, is composed of a great number of components, and since a great number of frames corresponding to every kind of standardized components for each class exist, if components of the same standard are represented in terms of frames, and data of a great number of frames is updated at every inference cycle, it is inevitable that inference time would increase due to the increase in process time for reconstituting interim memory.
To this end, the TREAT algorithm has been proposed. This algorithm does not maintain .beta. memory but maintains only .alpha. memory as interim memory so that a dynamic JOIN arithmetic operation is optimized at every inference cycle to improve the rate of memory management. In general, since the status value to be updated is large due to the execution of one rule in an inference in actual time, the TREAT algorithm is known as a high-speed condition judgment algorithm suited to a real-time process.
However, assuming that the TREAT algorithm is adopted in a large-scale artificial system, .alpha. memory is managed as interim memory increasing the computation needed to reconstitute this interim memory so that an increase in inference time is still inevitable. Because of the interim memory, these algorithms have many frames and hence are not suitable to a system in which data of a great number of frames needs to be updated.
A large-scale artificial system that has many frames and requires data of a great number of frames to be updated every inference process will now be described referring to a practical inference process. FIG. 9 shows a power supply route to various instruments in an electrical power system. 901 designates a power supply source; 902, a switch; and 903, 904 and 905 designate instruments which receive the power supply. One instrument 904 receives power via another instrument 903. For each instrument, it is necessary to define frames as shown in FIG. 9, increasing the number of the frames. In each frame, the slot named `voltage` represents the status of whether or not the instrument is receiving power. The slot named `supply` represents a set of instruments to which power is supplied from the instrument.
In this case, the inference process to discriminate as to which instrument happens to shut down when the switch 902 becomes out of order will now be considered. To realize such an inference process by rules, the rule to make a judgment of power failure will be such as "If the value of slot `voltage` is `Nil` and if the value of slot `voltage` of the frame stored in slot `supply` is `present`, substitute `Nil` for slot `voltage` of the frame."
The above-mentioned method can also be used, in this case, assuming that a demon having a character called `when-changed` is defined for slot `voltage` and that the value `Nil` is substituted for slot `voltage`, a message to request substitution of the value `Nil` for slot `voltage` in every frame stored in slot `supply` is transmitted. Thus in the process of inference, `voltage` slots of many frames are successively updated.
The inference process for judgment of power failure is to recognize the status of an object system given less information and knowledge concerning the constitution of the object system. As mentioned above, in a large-scale artificial system, there are many frames, and data of a great number of frames are updated by individual inference processes.
(2) Increase of Time Needed for State Recognition
In an expert system to be applied to an actual artificial system, there is a step to grasp the status of the actual artificial system, irrespective of its purpose. In a practical system, its status varies constantly; updating of knowledge resulting from such fluctuation is inevitable when performing a proper inference.
In a conventional expert system, if an inference is started externally by an instruction or the like, an inference engine first fetches the external status values and then makes a discrimination on the situation by using such external data, whereupon an inference for the original purpose is carried out. Otherwise, when it becomes necessary to grasp the situation during inference execution, the external status values are retrieved and recognized.
According to technology disclosed in, for example, "Expert System for Discrimination of Failure Section Based on Generalized Rules", Institute of Electrical Engineers of Japan 1988, PE-88-26, during executing an inference of a failure section in an electrical power system, the status of each relay is examined to determine the status of the previous step, and the section of protection of each relay is determined and recognized by inference.
Therefore, in a large-scale system in which there exist many situations to be grasped, discriminating the situation would take an unallowably long time.
3) High Load of Inference Engine due to Complexity of Knowledge according to Combined View Point
In an expert system to be applied to an actual large-scale system, as the purpose for inference becomes complex, like knowledge expressions are not always used even for the similar object system, thus requiring various knowledge expressions. This problem will now be described in connection with FIG. 10.
FIG. 10(a) is a block diagram (systematic diagram) showing an electric power system which comprises a substation A, a substation B and a power-transmission line C connecting the substations A and B. There are a pair of buses a and b in each substation A and B. Between each pair of buses a and b and the power transmission line C, there are located switches LS1-LS4 and breakers CB1-CB2, along with current transformers CT1-CT4 used as current measuring instruments.
To make an inference for a discrimination of failure in this system, the individual instruments need to be represented as frames corresponding to the arrangement shown in FIG. 10(b). To make an inference for making a system operation plan for changing the connection status of the instruments in this system, no measuring instrument is necessary so that the individual instruments need to be represented as frames corresponding to the arrangement shown in FIG. 10(c). To make a calculation of power flow, i.e., to calculate distribution of electrical energy, only knowledge about the buses as nodes and about the power transmission line is needed as shown in FIG. 10(d).
In the foregoing examples, the knowledge representing methods were suitable for various purposes. In an actual expert system, it is usual that these purposes would come up in combination. If knowledge representation and instance frames were therefore defined for every purpose, the larger the system, the larger the number of frames thus increasing the computation for condition judgment steps of a production system, and resulting in an increased inference time. In the meantime, if various purposes were accomplished by a small number of instance frames, rules become complex and increased in number thus increasing the number of inference steps to be made until the purpose is achieved.
As discussed above, in an expert system to be applied to an actual large-scale system, the inference engine would undertake a high load due to the complicated knowledge, thus increasing the inference time. In a practical system, object data is updated frequently like the status of the switches LS1, LS2, etc. of FIG. 10. In this case, it is necessary not only to update the slot value storing the updated status value, but also to update all the associated status values so as not to cause any contradiction. This is a significant problem particularly in an expert system adopting a real-time process. In a production system, however, no adequate method for solving this problem is known. Thus the conventional production system would encounter an increase of inference time when applied to an actual large-scale system.
In a public system such as an electric power system or a communication system, an increase of inference time means an increase in recovery time when a fault occurs, which is a serious problem.